SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Sentinel node</title>

</head>

Sentinel node

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about the computer programming construct. For the body part, see <a href="Sentinel_lymph_node" title="Sentinel lymph node">Sentinel lymph node</a>.</div>

<div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Sentinel_value" title="Sentinel value">sentinel value</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In computer programming, a sentinel node is a specifically designated <a href="Node_(computer_science)" title="Node (computer science)">node</a> used with <a href="Linked_list" title="Linked list">linked lists</a> and <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">trees</a> as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.

<div class="mw-heading mw-heading2"><h2 id="Benefits">Benefits</h2></div>

Sentinels are used as an alternative over using <a href="Null_pointer" title="Null pointer"><code>NULL</code></a> as the path terminator in order to get one or more of the following benefits:

<ul><li>Marginally increased speed of operations</li>

<li>Increased data structure <a href="Robustness_(computer_science)" title="Robustness (computer science)">robustness</a> (arguably)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Drawbacks">Drawbacks</h2></div>

<ul><li>Marginally increased memory usage, especially when linked list is short.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Search_in_a_linked_list">Search in a linked list</h3></div>

Below are two versions of a subroutine (implemented in the <a href="C_(programming_language)" title="C (programming language)">C programming language</a>) for looking up a given search key in a <a href="Linked_list#Singly_linked_list" title="Linked list">singly linked list</a>. The first one uses the <a href="Sentinel_value" title="Sentinel value">sentinel value</a> <code>NULL</code>, and the second one a (pointer to the) sentinel node <code>Sentinel</code>, as the end-of-list indicator. The declarations of the singly linked list data structure and the outcomes of both subroutines are the same.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>struct sll_node { // one node of the singly linked list

struct sll_node *next; // end-of-list indicator or -> next node

int key;

} sll, *first;

</pre></div>

<div class="mw-heading mw-heading4"><h4 id="First_version_using_NULL_as_an_end-of-list_indicator">First version using NULL as an end-of-list indicator</h4></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre>// global initialization

first = NULL; // before the first insertion (not shown)

struct sll_node *Search(struct sll_node *first, int search_key) {

struct sll_node *node;

for (node = first;

node != NULL;

node = node->next)

{

if (node->key == search_key)

return node; // found

}

// search_key is not contained in the list:

return NULL;

}

</pre></div>

The <code>for</code>-loop contains two tests (yellow lines) per iteration:

<li><code>if (node->key == search_key)</code>.</li></ul>

<div class="mw-heading mw-heading4"><h4 id="Second_version_using_a_sentinel_node">Second version using a sentinel node</h4></div>

The globally available pointer <code>sentinel</code> to the deliberately prepared data structure <code>Sentinel</code> is used as end-of-list indicator.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre>// global variable

sll_node Sentinel, *sentinel = &Sentinel;

// global initialization

sentinel->next = sentinel;

first = sentinel; // before the first insertion (not shown)

</pre></div>

Note that the pointer sentinel has always to be kept at the end of the list.

This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>struct sll_node *SearchWithSentinelnode(struct sll_node *first, int search_key) {

struct sll_node *node;

// Prepare the “node” Sentinel for the search:

sentinel->key = search_key;

for (node = first;

node->key != search_key;

node = node->next)

{}

// Post-processing:

if (node != sentinel)

return node; // found

// search_key is not contained in the list:

return NULL;

}

</pre></div>

The <code>for</code>-loop contains only one test (yellow line) per iteration:

<ul><li><code>node->key != search_key;</code>.</li></ul>

<div class="mw-heading mw-heading4"><h4 id="Python_implementation_of_a_circular_doubly-linked_list">Python implementation of a circular doubly-linked list</h4></div>

Linked list implementations, especially one of a circular, doubly-linked list, can be simplified remarkably using a sentinel node to demarcate the beginning and end of the list.

<ul><li>The list starts out with a single node, the sentinel node which has the next and previous pointers point to itself. This condition determines if the list is empty.</li>

<li>In a non-empty list, the sentinel node's next pointer gives the head of the list, and the previous pointer gives the tail of the list.</li></ul>

Following is a Python implementation of a circular doubly-linked list:

<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>class Node:

def __init__(self, data, next=None, prev=None):

self.data = data

self.next = next

self.prev = prev

def __repr__(self) -> str:

return f'Node(data={self.data})'

class LinkedList:

def __init__(self):

self._sentinel = Node(data=None)

self._sentinel.next = self._sentinel

self._sentinel.prev = self._sentinel

def pop_left(self) -> Node:

return self.remove_by_ref(self._sentinel.next)

def pop(self) -> Node:

return self.remove_by_ref(self._sentinel.prev)

def append_nodeleft(self, node):

self.add_node(self._sentinel, node)

def append_node(self, node):

self.add_node(self._sentinel.prev, node)

def append_left(self, data):

node = Node(data=data)

self.append_nodeleft(node)

def append(self, data):

node = Node(data=data)

self.append_node(node)

def remove_by_ref(self, node) -> Node:

if node is self._sentinel:

raise Exception('Can never remove sentinel.')

node.prev.next = node.next

node.next.prev = node.prev

node.prev = None

node.next = None

return node

def add_node(self, curnode, newnode):

newnode.next = curnode.next

newnode.prev = curnode

curnode.next.prev = newnode

curnode.next = newnode

def search(self, value):

self._sentinel.data = value

node = self._sentinel.next

while node.data != value:

node = node.next

self._sentinel.data = None

if node is self._sentinel:

return None

return node

def __iter__(self):

node = self._sentinel.next

while node is not self._sentinel:

yield node.data

node = node.next

def reviter(self):

node = self._sentinel.prev

while node is not self._sentinel:

yield node.data

node = node.prev

</pre></div>

Notice how the <code>add_node()</code> method takes the node that will be displaced by the new node in the parameter <code>curnode</code>. For appending to the left, this is the head of a non-empty list, while for appending to right, it is the tail. But because of how the linkage is set up to refer back to the sentinel, the code just works for empty lists as well, where <code>curnode</code> will be the sentinel node.

<div class="mw-heading mw-heading3"><h3 id="Search_in_a_binary_tree">Search in a binary tree</h3></div>

General declarations, similar to article <a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>struct bst_node { // one node of the binary search tree

struct bst_node *child[2]; // each: ->node or end-of-path indicator

int key;

} ;

struct bst { // binary search tree

struct bst_node *root; // ->node or end-of-path indicator

} *BST;

</pre></div>

The globally available pointer <code>sentinel</code> to the single deliberately prepared data structure <code>Sentinel = *sentinel</code> is used to indicate the absence of a child.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre>// global variable

bst_node Sentinel, *sentinel = &Sentinel;

// global initialization

Sentinel.child[0] = Sentinel.child[1] = sentinel;

BST->root = sentinel; // before the first insertion (not shown)

</pre></div>

Note that the pointer sentinel has always to represent every leaf of the tree.

This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre>struct bst_node *SearchWithSentinelnode(struct bst *bst, int search_key) {

struct bst_node *node;

// Prepare the “node” Sentinel for the search:

sentinel->key = search_key;

for (node = bst->root;;) {

if (search_key == node->key)

break;

if search_key < node->key:

node = node->child[0]; // go left

else

node = node->child[1]; // go right

}

// Post-processing:

if (node != sentinel)

return node; // found

// search_key is not contained in the tree:

return NULL;

}

</pre></div>

<dl><dt>Remarks</dt>

<ol><li>With the use of SearchWithSentinelnode searching loses the <a href="File-system_permissions" title="File-system permissions">read-only</a> property. This means that in applications with <a href="Concurrent_computing" title="Concurrent computing">concurrency</a> it has to be protected by a <a href="Mutex" class="mw-redirect" title="Mutex">mutex</a>, an effort which normally exceeds the savings of the sentinel.</li>

<li>SearchWithSentinelnode does not support the tolerance of duplicates.</li>

<li>There has to be exactly one “node” to be used as sentinel, but there may be extremely many pointers to it.</li></ol>

<ul><li><a href="Canary_value" class="mw-redirect" title="Canary value">Canary value</a></li>

<li><a href="Elephant_in_Cairo" title="Elephant in Cairo">Elephant in Cairo</a></li>

<li><a href="Guard_(computer_science)" title="Guard (computer science)">Guard (computer science)</a>, a boolean expression that must evaluate to true if the program execution is to continue in the branch in question</li>

<li><a href="Magic_number_(programming)" title="Magic number (programming)">Magic number (programming)</a></li>

<li><a href="Magic_string" title="Magic string">Magic string</a></li>

<li><a href="Null_object_pattern" title="Null object pattern">Null object pattern</a></li>

<li><a href="Semipredicate_problem" title="Semipredicate problem">Semipredicate problem</a></li>

<li><a href="Sentinel_value" title="Sentinel value">Sentinel value</a></li>

<li><a href="Time_formatting_and_storage_bugs" title="Time formatting and storage bugs">Time formatting and storage bugs</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-09-25" href="https://en.wikipedia.org/wiki/?title=Sentinel_node&oldid=1247715853">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>